package nk.tree;

import java.util.Arrays;

public class AB14 {

    public int miniSpanningTree (int n, int m, int[][] cost) {

        int[][] graph = new int[n + 1][n + 1]; //构建一个无向图
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= n ; j++) {
                graph[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < cost.length; i++) {
          if (graph[cost[i][0]][cost[i][1]] > cost[i][2]) {
              graph[cost[i][0]][cost[i][1]] = cost[i][2];
              graph[cost[i][1]][cost[i][0]] = cost[i][2];
          }
        }

        int minCost = 0;
        boolean[] inTreeSet = new boolean[n + 1];
        inTreeSet[1] = true; //首先把节点1放入最新生成树
        int inTreeCnt = 1;
        int[] dist = new int[n + 1]; //节点i到最小生成树的代价
        for (int i = 2; i <=n ; i++) { //更新节点到最新生成树的代价
            dist[i] = graph[1][i];
        }
        while (inTreeCnt < n) {
            //找出不在生成树内的距离最小生成树代价最小的节点
            int minDist = Integer.MAX_VALUE;
            int index = 0;
            for (int i = 1; i <= n ; i++) {
                if (!inTreeSet[i] && dist[i] < minDist) {
                    index = i;
                    minDist = dist[i];
                }
            }
            //将找到的距离生成树最近的节点加入到生成树
            inTreeSet[index] = true;
            minCost += minDist;
            inTreeCnt++;
            //更新其他节点到最小生成树的代价
            for (int i = 1; i <= n ; i++) {
                if (!inTreeSet[i] && dist[i] > graph[index][i]) {
                    dist[i] = graph[index][i];
                }
            }
        }
        return minCost;
    }



}
